﻿namespace CSharpExt.Util
{
    /// <summary>
    /// Questa classe ha il compito di fornire il prossimo numero primo a partire dal numero
    /// passato come argomento.
    /// 
    /// L'implementazione e' semplice, poiche' in generale non potranno mai essere trattati numeri
    /// piu' grandi di 2^31-1.
    /// 
    /// Per controllare se un numero e' primo, si controlla se e' divisibile per qualche numero 
    /// dispari, a partire da 3 e minore di Sqrt(n). Quindi, al piu' potranno essere fatti 2^14 
    /// (16384) test, ma in generale saranno sempre molti di meno.
    /// </summary>
    public static class Primes
    {
        public static int NextPrime(int n)
        {
            if (n < 3)
                return n + 1;

            n = n + n%2 + 1;
            while (!IsPrime(n))
                n += 2;
            return n;
        }

        public static int Sqrt(int n)
        {
            int x = 0;
            int y = n;
            
            while ((x < y ? y - x : x - y) > 1)
            {
                x = y;
                y = (x + n / x) / 2;
            }

            return y;
        }

        public static bool IsPrime(int n)
        {
            if (n%2 == 0)
                return false;

            //int l = Sqrt(n);
            for (int p = 3; p*p <= n; p += 2)
            {
                if (n%p == 0)
                    return false;
            }
            return true;
        }
    }
}